package com.wangyadong.hobby.schedule.jobtask.tree.example;

import com.wangyadong.hobby.schedule.jobtask.LinkedQueue;
import com.wangyadong.hobby.schedule.jobtask.Queue;
import com.wangyadong.hobby.schedule.jobtask.tree.Position;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * <p>
 *
 * @author <714037465@qq.com>
 * @since 2018/10/813:13
 **/
public class LinkedBinaryTree<E> extends AbstractBinaryTree<E> {
    private int size = 0;
    private Node root = null;

    private static class Node<E> implements Position<E> {
        private E element;
        private Node left;
        private Node right;
        private Node parent;

        public Node() {
        }

        public Node(E element, Node left, Node right, Node parent) {
            this.element = element;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }

        public E getElement() {
            return element;
        }

        public void setElement(E element) {
            this.element = element;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public Node getParent() {
            return parent;
        }

        public void setParent(Node parent) {
            this.parent = parent;
        }
    }

    protected Node createNode(E element, Node left, Node right, Node parent) {
        Node node = new Node(element, left, right, parent);
        return node;
    }

    @Override
    public Iterator iterator() {
        return new ElementIterator();
    }

    private Node valadate(Position position) {

        if (!(position instanceof Node)) {
            throw new IllegalArgumentException("");
        }
        Node node = (Node) position;
        if (node == node.getParent()) {
            throw new IllegalArgumentException("");
        }
        return node;
    }

    @Override
    public int size() {
        return size;
    }


    public Node addRoot(E element) {
        root = createNode(element, null, null, null);
        size = 1;
        return root;
    }

    public Node addLeft(Position position, E element) {
        Node parent = valadate(position);
        Node node = createNode(element, null, null, parent);
        parent.setLeft(node);
        size++;
        return node;
    }

    public Node addRight(Position position, E element) {
        Node parent = valadate(position);
        Node node = createNode(element, null, null, parent);
        parent.setRight(node);
        size++;
        return node;
    }

    public Node remove(Position position) {
        Node valadate = valadate(position);
        if (childNum(position) == 2) {
            throw new IllegalArgumentException(" has two child can't remove");
        }
        Node child = valadate.getLeft() != null ? valadate.getLeft() : valadate.getRight();
        if (null != child) {
            child.setParent(valadate.getParent());
        }
        Node parent = valadate.getParent();
        if (valadate == root()) {
            valadate = parent;
        } else {
            if (left(position) != null) {
                parent.setLeft(child);
            } else {
                parent.setRight(child);
            }

        }
        size--;
        valadate.setParent(valadate);
        valadate.setRight(null);
        valadate.setLeft(null);
        valadate.setElement(null);

        return valadate;
    }

    @Override
    public Iterable<Position<E>> positions() {
        return inorder();
    }


    ///////////////////////////////////////////////
    @Override
    public Position root() {
        return root;
    }


    @Override
    public Position<E> left(Position position) throws IllegalArgumentException {
        Node valadate = valadate(position);
        return valadate.getLeft();
    }


    @Override
    public Position<E> right(Position position) throws IllegalArgumentException {
        Node valadate = valadate(position);
        return valadate.getRight();
    }

    @Override
    public Position parent(Position position) throws IllegalArgumentException {
        Node valadate = valadate(position);
        return valadate.getParent();
    }

    private class ElementIterator implements Iterator<E> {
        Iterator<Position<E>> posIterator = positions().iterator();

        public boolean hasNext() {
            return posIterator.hasNext();
        }

        public E next() {
            return posIterator.next().getElement();
        } // return element!

        public void remove() {
            posIterator.remove();
        }
    }

    /***
     * preOrder 先访问root ，在访问子节点的root，递归访问
     *
     */

    public Iterable preOrder() {
        List<Position<E>> snapshot = new ArrayList<>();
        if (!isEmpty()) {
            preOrder(root(), snapshot);
        }
        return snapshot;
    }

    private void preOrder(Position<E> position, List<Position<E>> snapshot) {
        snapshot.add(position);
        for (Position<E> p : child(position)) {
            preOrder(p, snapshot);
        }
    }

    /***
     * postOrder
     * because it recursively traverses the subtrees rooted at the children of the root first, and
     then visits the root (hence, the name “postorder”).
     后续排序就是先访问子树的根节点，最后在访问root节点
     *
     */
    private void postorderSubtree(Position<E> p, List<Position<E>> snapshot) {
        for (Position<E> c : child(p))
            postorderSubtree(c, snapshot);
        snapshot.add(p); // for postorder, we add position p after exploring subtrees
    }

    /*** Returns an iterable collection of positions of the tree, reported in postorder. **/
    public Iterable<Position<E>> postorder() {
        List<Position<E>> snapshot = new ArrayList<>();
        if (!isEmpty())
            postorderSubtree(root(), snapshot); // fill the snapshot recursively
        return snapshot;
    }
    /**
     *总的来说前序和后续都是高效的遍历算法，和计算深度的方法类型，他的运行时间为：O(n)
     * where Cp is the number of children 就是子孙的数量，这种算法会越老越好，
     *
     *
     *
     */


    /***
     * inOrder 先访问root ，在访问子节点的root，递归访问
     *
     */
    public Iterable<Position<E>> inorder() {
        List<Position<E>> snapshot = new ArrayList<>();
        if (!isEmpty())
            inorderSubtree(root(), snapshot); // fill the snapshot recursively
        return snapshot;
    }


    private void inorderSubtree(Position<E> position, List<Position<E>> snapshot) {
        if (left(position) != null)
            inorderSubtree(left(position), snapshot);
        snapshot.add(position);
        if (right(position) != null) {
            inorderSubtree(right(position), snapshot);
        }
    }

    /***
     * bread-first 先访问root ，在访问子节点的root，递归访问
     *
     */

    public Iterable breadFirst() {
        List<Position<E>> snapshot = new ArrayList<>();
        if (!isEmpty()) {
            Queue<Position<E>> fringe = new LinkedQueue<>();
            fringe.enqueue(root());
            while (!fringe.isEmpty()) {
                Position<E> dequeue = fringe.dequeue();
                snapshot.add(dequeue);
                for (Position position : child(dequeue)) {
                    fringe.enqueue(position);
                }
            }
        }
        return snapshot;
    }

    public static <E> void printPreorderIndent(Tree<E> T, Position<E> p, int d) {
//        System.out.println(spaces(2∗d) + p.getElement()); // indent based on d
        for (Position<E> c : T.child(p))
            printPreorderIndent(T, c, d + 1); // child depth is d+1
    }

    public static int diskSpace(Tree<Integer> T, Position<Integer> p) {
        int subtotal = p.getElement(); // we assume element represents space usage
        for (Position<Integer> c : T.child(p))
            subtotal += diskSpace(T, c);
        return subtotal;
    }

    public static void main(String[] args) {
        LinkedBinaryTree tree = new LinkedBinaryTree();
        tree.addRoot("root");
        tree.addLeft(tree.root(), "left-1");
        tree.addRight(tree.root(), "right-1");
        tree.addLeft(tree.left(tree.root()), "sun-left-1");
        tree.addRight(tree.right(tree.root()), "sun-right-1");

        tree.addLeft(tree.left(tree.left(tree.root())), "sun-left-2");
        tree.addRight(tree.right(tree.right(tree.root())), "sun-right-2");
        Iterable iterable = tree.breadFirst();
        Iterator<Position> iterator = iterable.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next().getElement());
        }
        System.out.println(tree);

    }
}
